package offer;
import java.util.*;
/**
 * Creared with IntelliJ IDEA.
 * Description:
 * User:yxd
 * Date:2022-07-15
 * Time:20:14
 */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;

    }

}
public class JZ77 {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if(pRoot == null)return ret;
        //第一行从左向右，就是顺着来，第二行是从右向左就是逆着来就可以使用栈记录，然后不断打印

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        int index = 1;
        while(!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            if(index % 2 == 1){
                int size = queue.size();
                while(size-- != 0){
                    TreeNode cur = queue.poll();
                    list.add(cur.val);
                    if(cur.left != null){
                        queue.add(cur.left);
                    }
                    if(cur.right != null){
                        queue.add(cur.right);
                    }
                }
            }else{
                Stack<TreeNode> stack = new Stack<>();
                int size = queue.size();
                while(size-- != 0){
                    TreeNode cur = queue.poll();
                    stack.add(cur);
                    if(cur.left != null){
                        queue.add(cur.left);
                    }
                    if(cur.right != null){
                        queue.add(cur.right);
                    }
                }
                while(!stack.isEmpty()){
                    list.add(stack.pop().val);
                }
            }
            index ++;
            ret.add(new ArrayList<>(list));

        }
        return ret;
    }
}
